package graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 *@description 课程表 II
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_210 {

    @Test
    public void test(){
        findOrder(2,new int[][]{new int[]{1,0}});
    }

   class Node{
       int value;
       List<Edge> edges;
       int inNum=0;
       int visited;

       public Node(int value) {
           this.value = value;
           this.edges = new ArrayList<>();
           this.inNum = 0;
           this.visited = 0;
       }
   }
   class Edge{
       Node from;
       Node to;

       public Edge(Node from, Node to) {
           this.from = from;
           this.to = to;
       }
   }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //1. 定义
        List<Integer> list = new ArrayList<>();
        Map<Integer,Node> nodeMap = new HashMap<>();
        Boolean flag = true;
        //2. node加入nodeMap
        for (int i = 0; i < numCourses; i++) {
            nodeMap.put(i,new Node(i));
        }
        //3. node加入edge
        for (int i = 0; i < prerequisites.length; i++) {
            Node from = nodeMap.get(prerequisites[i][1]);
            Node to = nodeMap.get(prerequisites[i][0]);
            from.edges.add(new Edge(from,to));
            to.inNum++;
        }
        //4. 循环，删去节点
        while (flag){
            flag=false;
            for (Node node : nodeMap.values()) {
                if (node.inNum==0 && node.visited==0){
                    list.add(node.value);
                    update(node,nodeMap);
                    flag=true;
                }
            }
        }
        //5. 返回结果
        if (list.size()!=numCourses){
            return new int[0];
        }else {
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                res[i] = list.get(i);
            }
            return res;
        }

    }

    private void update(Node node, Map<Integer, Node> nodeMap) {
        for (Edge edge : node.edges) {
            edge.to.inNum--;
        }
        //nodeMap.remove(node.value);
        node.visited=1;
    }

}
